#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N = 32;
const int CN2 = N * (N - 1) / 2;

string s;
int K;

ll dp[N][N][N][CN2];

int main() {
    cin >> s >> K;

    int n = s.size();

    K = min(K, n * (n - 1) / 2);
    vector<int> kPos, ePos, yPos;

    for (int i = 0; i < n; i++) {
        char ch = s[i];
        if (ch == 'K') kPos.push_back(i);
        if (ch == 'E') ePos.push_back(i);
        if (ch == 'Y') yPos.push_back(i);
    }

    int kCnt = kPos.size(), eCnt = ePos.size(), yCnt = yPos.size();

    dp[0][0][0][0] = 1;

    for (int i = 0; i < n; i++) {
        for (int e = 0; e <= eCnt; e++) {
            for (int y = 0; y <= yCnt; y++) {
                int kk = i - e - y;
                if (kk < 0 || kk > kCnt) continue;

                for (int sw = 0; sw <= K; sw++) {
                    // 这个状态对后面没贡献
                    if (!dp[i][e][y][sw]) continue;

                    // 试着省略?
                    if (kk < kCnt) {
                        int moveSteps = 0; // 把i+1位置的K往左交换
                        for (int l = 0; l < e; l++) if (ePos[l] > kPos[kk]) moveSteps++;
                        for (int l = 0; l < y; l++) if (yPos[l] > kPos[kk]) moveSteps++;

                        if (sw + moveSteps <= K) dp[i + 1][e][y][sw + moveSteps] += dp[i][e][y][sw];
                    }

                    if (e < eCnt) {
                        int moveSteps = 0;
                        for (int l = 0; l < kk; l++) if (kPos[l] > ePos[e]) moveSteps++;
                        for (int l = 0; l < y; l++) if (yPos[l] > ePos[e]) moveSteps++;

                        if (sw + moveSteps <= K) dp[i + 1][e + 1][y][sw + moveSteps] += dp[i][e][y][sw];
                    }

                    if (y < yCnt) {
                        int moveSteps = 0;
                        for (int l = 0; l < kk; l++) if (kPos[l] > yPos[y]) moveSteps++;
                        for (int l = 0; l < e; l++) if (ePos[l] > yPos[y]) moveSteps++;

                        if (sw + moveSteps <= K) dp[i + 1][e][y + 1][sw + moveSteps] += dp[i][e][y][sw];
                    }
                }
            }
        }
    }

    ll res = 0;

    for (int i = 0; i <= K; i++) res += dp[n][eCnt][yCnt][i];

    cout << res << endl;
    return 0;
}